package singleNumberIII;



/*
 * 260 Single Number III
 * 位运算进阶题
 * 思路
 * 1.全数组xor得出A xor B 结果
 * 2.根据xor结果可得A与B的某个二进制位相同（00、11）或不同（10、01）
 * 3.拆分数组，提取xor中为1的某位，将数组进行拆分，相同的数必然被分入同一组，而A与B由于在那位不同，会被分入不同的组*
 * 4.将问题转化为两个SingleNumberI问题
 */
public class Solution {
    public int[] singleNumber(int[] nums) {
       int[] res = new int[2];
       if (nums == null || nums.length == 0) {
            return res;
       }
       int a = 0,b=0;
       int xor=0;
       for (int i=0;i<nums.length;i++)
    	   xor=xor ^ nums[i];
       int n = xor & (~(xor-1)); //取出xor中最后一位1
       for (int i=0;i<nums.length;i++){
    	   if ((n & nums[i])==0)
    		   a=a ^ nums[i];
    	   else
    		   b=b ^ nums[i];
       }

       return(new int[]{a,b});
    }
    public static void main(String args[]){
    	Solution so=new Solution();
    	int[] nums=new int[]{1, 2, 1, 3, 2, 5};
    	System.out.println(so.singleNumber(nums)[0]);
    }
}
